package main

// 解法1： 就是纯粹的四层嵌套for循环暴力破解解决~~  数据规模不大
func countQuadruplets(nums []int) int {
	rst := 0
	// 2. 暴力找四个数
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			for k := j + 1; k < len(nums); k++ {
				for m := k + 1; m < len(nums); m++ {
					if nums[i]+nums[j]+nums[k] == nums[m] {
						rst += 1
					}
				}
			}
		}
	}
	return rst
}

// 原理都懂，但是自己写时候才会发现问题
// hash d + 三层for循环 （自己的错误解答）
// 消除掉嵌套的四层循环，保障复杂度
// 最常用的就是线性查找 优化掉。 可hash
// nums[a] + nums[b] + nums[c] == nums[d], d > c ，用hash算出所有d
func countQuadruplets(nums []int) int {
	rst := 0
	// 1. 求 nums[d] 的 map
	dMap := make(map[int]int)
	for d := 3; d < len(nums); d++ {
		dMap[nums[d]] += 1
	}
	// 2. 三层暴力找 a, b, c
	for a := 0; a < len(nums); a++ {
		for b := a + 1; b < len(nums); b++ {
			for c := b + 1; c < len(nums)-1; c++ {
				//  查找是否满足
				temp := nums[a] + nums[b] + nums[c]
				if num, ok := dMap[temp]; ok {
					rst += num
					// 去掉遍历过的 d位置
					dMap[temp] -= 1
				}
			}
		}
	}
	return rst
}

// 正确写法
// 消除掉嵌套的四层循环，保障复杂度
// 最常用的就是线性查找 优化掉。 可hash
// nums[a] + nums[b] + nums[c] == nums[d], d > c ，用hash算出所有d
func countQuadruplets(nums []int) int {
	rst := 0
	n := len(nums)
	// 1. 求 nums[d] 的 map
	dMap := make(map[int]int)
	// 2. 三层暴力找 a, b, c
	// 从后向前找c， 避免C的删除问题
	for c := n - 2; c >= 2; c-- {
		dMap[nums[c+1]] += 1
		for a := 0; a < c; a++ {
			for b := a + 1; b < c; b++ {
				//  查找是否满足
				temp := nums[a] + nums[b] + nums[c]
				if cnt, ok := dMap[temp]; ok {
					rst += cnt
				}
			}
		}
	}
	return rst
}

// 上面是 逆序枚举 c， 将式子变为： nums[a]+nums[b]=nums[d]−nums[c]
// 逆序遍历 b，  hash nums[d]−nums[c] 的结果。
func countQuadruplets(nums []int) int {
	ans := 0
	cnt := map[int]int{}
	for b := len(nums) - 3; b >= 1; b-- {
		for _, x := range nums[b+2:] {
			cnt[x-nums[b+1]]++
		}
		for _, x := range nums[:b] {
			if sum := x + nums[b]; cnt[sum] > 0 {
				ans += cnt[sum]
			}
		}
	}
	return ans
}
